package com.company.algo.tree.BST;

public class NumOfBSTs {
    int[][] memo;   //备忘录

    public int numTrees(int n) {
        memo = new int[n+1][n+1];
        return count(1,n);
    }

    //定义：闭区间[lo,hi]的数字能组成count(lo,hi)种BST
    int count(int lo, int hi){
        if (lo>hi) return 1;
        //查备忘录
        if (memo[lo][hi] != 0){
            return memo[lo][hi];
        }
        int res = 0;
        for (int i = lo; i <= hi; i++) {
            //以i为根节点
            int left = count(lo, i-1);
            int right = count(i+1, hi);
            res += left * right;
        }
        //将结果存入备忘录
        memo[lo][hi] = res;
        return res;
    }

    public static void main(String[] args) {
        NumOfBSTs Main = new NumOfBSTs();
        System.out.println(Main.numTrees(3));
    }
}
